package com.xj.algorithm.leetcode;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 将有序数组转换为平衡二叉搜索树
 * 左右子树的高度差在不超过1
 */
public class L108_有序数组转换为平衡二叉搜索树 {

    /**
     * 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
     *
     * 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
     *
     * 示例:
     *
     * 给定有序数组: [-10,-3,0,5,9],
     *
     * 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
     *
     *       0
     *      / \
     *    -3   9
     *    /   /
     *  -10  5
     */
    public static void main(String[] args) {
        int[] nums=new int[]{-10,-3,0,5,9};
        TreeNode root=sortedArrayToBST(nums);

        Queue<TreeNode> queue=new ArrayDeque();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node=queue.poll();
            System.out.println(node.val);
            if(node.left!=null){
                queue.add(node.left);
            }
            if(node.right!=null){
                queue.add(node.right);
            }
        }
    }

    //精彩解法：递归。已经是有序的了，找到根，拆分左右子树
    public static TreeNode sortedArrayToBST(int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }
        return createSubTree(nums, 0, nums.length - 1);
    }

    //递归方法
    public static TreeNode createSubTree(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = start + (end - start) / 2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = createSubTree(nums, start, mid - 1);
        node.right = createSubTree(nums, mid + 1, end);
        return node;
    }
}
